/*
 * @lc app=leetcode.cn id=738 lang=cpp
 *
 * [738] 单调递增的数字
 */

// @lc code=start
class Solution
{
private:
    int calnum(int n, int size)
    {
        int res = 0;
        for (int i = 0; i <= size; i++)
        {
            res += n * pow(10, i);
        }
        return res;
    }

public:
    int monotoneIncreasingDigits(int n)
    {
        //找出<=0的最大单调递增数
        //n>=0
        int res = 0;
        int nn = n;
        //局部最优推出全局最优 从最大位开始选择最大的数
        vector<int> num; //存储n的各位数字
        while (nn)
        {
            num.push_back(nn % 10);
            nn /= 10;
        }
        //得到的num开始是个位
        vector<int> resnum(num.size()); //记录最后结果的各位数字
        long long pre = 0;
        for (int i = num.size() - 1; i >= 0; i--)
        {
            int tmp = 9;
            //不加下面这个判断就溢出了
            if (i == num.size() - 1)
            {
                tmp = num[i];
            }
            while (tmp >= 0 && pre + calnum(tmp, i) > n)
            {
                tmp--;
            }
            //当前tmp为当前为最大数
            resnum[i] = tmp;
            pre += tmp * pow(10, i);
        }
        for (int i = 0; i < resnum.size(); i++)
        {
            res += resnum[i] * pow(10, i);
        }
        return res;
    }
};
// @lc code=end
